# -*- coding: UTF-8 -*-
from typing import List
from leetcode_helper import TestcaseHelper, SolutionBase, ListNode, array_to_list, list_to_array


class Solution(SolutionBase):
    # 解题的方法，命名和Leetcode的保持一致即可
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def merge_two_list(l1: ListNode, l2: ListNode) -> ListNode:
            dummy = ListNode(0)
            curr = dummy

            while l1 and l2:
                if l1.val < l2.val:
                    curr.next = l1
                    curr = l1
                    l1 = l1.next
                else:
                    curr.next = l2
                    curr = l2
                    l2 = l2.next

            if l1:
                curr.next = l1
            if l2:
                curr.next = l2

            return dummy.next

        def merge(_lists: List[ListNode]) -> ListNode:
            if len(_lists) == 1:
                return _lists[0]
            elif len(_lists) == 0:
                return None
            else:
                left = 0
                right = len(_lists) - 1
                new_lists = []
                while left < right:
                    left_list = _lists[left]
                    right_list = _lists[right]
                    new_lists.append(merge_two_list(left_list, right_list))
                    left += 1
                    right -= 1

                if left == right:
                    new_lists.append(_lists[left])

                return merge(new_lists)

        return merge(lists)


if __name__ == '__main__':
    solution = Solution()

    # 按照leetcode的题目说明，将基本的test case填入
    # 每条case的最后一个元素是正确的结果，即期待的结果
    # 使用元组来保存输入的数据，期待的结果
    testcases = [
        ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
        ([], []),
        ([[]], [])
    ]

    for case_item in testcases:
        # 获取测试用的case和期待的执行结果
        input1 = case_item[0]
        expect = case_item[len(case_item) - 1]

        lists = []
        for item in input1:
            item_list = array_to_list(item)
            lists.append(item_list)

        exec_result = solution.mergeKLists(lists)

        # 判断执行结果，输出提示信息
        check_result = solution.check_result(expect, list_to_array(exec_result))
        TestcaseHelper.print_case(check_result, case_item, list_to_array(exec_result))

